论文翻译 FLAME Differentially Private Federated Learning in the Shuffle Model

联邦学习(Federation Learning，FL )是一种很有前途的机器学习范式，它可以使分析器在不收集用户原始数据的情况下训练模型。为了保证用户隐私，差分隐私联邦学习得到了广泛的研究。现有的工作主要基于差分隐私的中心模型（curator model） 或本地模型（local model）。然而，两者都有利有弊。curator model允许更高的准确性，但需要可信的分析器。在local model中，用户将本地数据随机化后发送给分析器，虽然不需要可信分析器，但准确率有限。在这项工作中，通过利用最近提出的差分隐私混洗模型中的隐私放大（privacy amplification）效应，我们实现了两个模型的最佳方式，即平衡了curator model中的准确性和不依赖任何可信方的强隐私性。我们首先提出了shuffle模型中的联邦学习框架和在已有工作基础上扩展的一种简单协议（SS-Simple）。我们发现SS-Simple仅在联邦学习中提供了不充分的隐私放大效应，因为模型参数的维度相当大。为了解决这一问题，我们提出了一种增强型协议（SS-Double），通过欠采样来强化隐私放大效应。进一步，当模型规模大于用户数量时，为了提高效用，我们提出了一种采用梯度稀疏技术的改进协议（SS-Topk）。我们还对所提协议的隐私放大效应进行了理论分析和量化评估。在real-world数据集上的实验验证了SS-Topk比基于本地模型的联邦学习提高了60.7 %的测试准确率。值得注意的是，SS-Topk甚至比基于curator model的联邦学习提高了33.94 %的准确率。与非私有联邦学习相比，我们的协议SS-Topk在下仅损失了1.48 %的准确率。

联邦学习（Federation Learning，FL ）是一种很有前途的机器学习范式，它可以使分析器在不收集用户原始数据而只进行本地更新的情况下训练一个中心模型。然而，已有研究表明，共享原始的本地更新可能会损害用户的隐私。为此，差分隐私联邦学习（differentially private federated learning）被广泛研究以提供形式隐私。现有的工作主要基于差分隐私的curator model( DP )或 local model( LDP )。基于curator model的FL ( DP-FL ) 会得到更好的准确率，但依赖于可信分析器来收集原始的本地更新。基于local model的FL ( LDP-FL ) 保留了很强的本地隐私，因为用户在将本地更新发送到不可信分析器之前对其进行随机化处理；但其效用较低。具体来说，对于隐私预算为的个用户的一项比特求和任务，DP的误差可以达到；而LDP的误差是以为界的。

最近提出的安全混洗模型( secure shuffle model, SS )可以同时实现两种模型的最佳方式，即curator model的准确性和local model的强隐私性。shuffle模型在用户和分析器之间引入了一个混洗器( 如Figure 1(b)所示 )，在将用户的本地随机数据发送到分析器之前对其进行置换。混洗模型的精度增益由隐私放大效应（privacy amplification effect） 得到，这表明在差分隐私的中心视图中，经过混洗的本地随机发生器的（即,匿名化）输出比没有混洗的输出提供了更强的（增强的）隐私。相应地，在混洗模型中需要更少的本地噪声来保护与不可信分析器相同级别的隐私。

然而，在联邦学习中如何使用shuffle模型尚不清楚。尽管少数工作已经研究了诸如比特/实数求和以及直方图等基本任务，但是现有的协议可能并不适用于多维状态的聚合联邦学习。

更新向量的维度以维度因子加剧了本地噪声引起的误差。此外，由于参与一次迭代的用户数量通常为好几千，因此聚合操作会升级为高维任务。我们通过做出以下贡献来解决上述挑战：

我们首次在shuffle模型中提出了一个联邦学习框架FLAME，使得用户享有较强的隐私性，分析器享有模型的准确性。我们首先在FLAME中通过明确信任边界（trust boundary）和细粒化信任分离（trust separation）来形式化我们的隐私目标（表1），然后我们通过扩展一维任务提出了SS - Simple协议。

我们发现，尽管SS - Simple可以实现隐私放大，但是增强的幅度随着本地更新的维度增大而减小（定理2）。

为了减轻这一挑战，我们提出了SS - Double协议，通过子采样来强化隐私放大。正如我们注意到的，通过子采样的增强可能与混洗不兼容，于是我们提出了一种新的虚拟填充（dummy padding）方法并用形式化证明（定理3和定理4）来桥接这两种增强效应。我们证明了SS - Double协议比SS - Simple协议具有数十倍的隐私放大效果（图3）。

SS - Double协议的一个问题是随机子采样对所有维度一视同仁，从而有可能丢弃"重要"维度。为了进一步提高在高维情况下的效用，我们基于梯度稀疏化的思想设计了一个改进的协议——SS - Topk。一个挑战是，局部更新向量中Top的元素的索引可能会揭示相对于混洗者敏感的信息，因为选择是数据依赖的。我们通过将索引隐私（index privacy）形式化来量化这种隐私威胁，并设计了一种在索引隐私和效用之间灵活权衡的方法。我们注意到索引隐私不会损害对分析器的隐私保护。

最后，我们在真实数据集上进行实验，验证所提出的协议的有效性。结果表明，本文提出的SS - Double中的双重增强3效应和SS - Topk中的私有维度选择显著提高了学习准确率。在不依赖任何可信方的情况下，SS - Topk比基于FL的curator model提高了33.94 %的准确率。与非私有FL相比，SS - Topk在、下仅损失1.48 %的准确率。

在Curator Model中，可信分析器收集用户的原始数据(例如局部更新)，并执行私有机制以保证不同的私有输出。隐私保护的目标是通过替换一个用户的数据来实现两个相邻数据集的任何输出不可区分，记为。我们有如下定义：

差分隐私机制的定义 ：设一种机制满足差分隐私，如果对于任意两个相邻数据集和任意子集，有

然而，curator model假设可信分析器收集原始数据的可用性。定义2中的本地差分隐私不依赖于任何可信方，因为用户向服务器发送随机数据。若满足，则观察收集到的结果或其总和蕴含

本地差分隐私的定义：设一种机制满足本地差分隐私，如果对于任意两个输入和任意输出，有。

混洗模型的协议由三个部分组成：，如图1 ( b )所示。

现有的工作主要关注每个用户持有一维数据的基本任务。记个用户的数据为数据集。每个用户运行一个随机数发生器，将本地数据扰动为满足LDP的条消息。不失一般性，我们重点研究了的单消息协议。混洗器用均匀随机置换在接收到的消息上执行。解析函数将混洗后的消息作为输入，输出解析结果。

混洗模型中的隐私目标是保证满足DP，因为由不可信分析器执行，不必保护用户隐私。由后处理性质（post-processing property），协议达到了与相同的隐私级别。因此，我们重点分析了和的不可区分性。的隐私可以被"放大"。也就是说，当每个用户在中应用本地隐私预算时，可以实现更强的DP隐私，且。与local模型相比，shuffle模型可以用更少的噪声来达到相同的隐私级别。“隐私毯子”为单消息协议提供了一个最优放大界。分析的直觉是将输出分布线性分解为真实数据分布和均匀随机"隐私毯"分布。表示从毯子分布输出一个元素的概率。利用算法1中的本地随机数发生器，其中，将输入值编码到离散域中，然后进行随机化。运行一个置换后，聚合混洗结果，并参照以下进行去偏

算法1的隐私放大边界如引理1所示，通用随机数发生器的效果在推论1中提取。对于域上具有Laplace机制的随机数发生器，。通过数值评估可以访问更严格的边界(即,更大的放大)。

引理 1：对于，若满足LDP，则对于我们有，其中

推论 1：在shuffle模型中，若是LDP的，其中。满足DP当。

组成的属性对于差分隐私的curator和local模型都是通用的。

引理 2： ，DP机制族在自适应组合下满足DP

引理 3： ，DP机制族在自适应组合下满足DP

在引理4中，一个从数据库中随机抽取元素而不进行替换的机制导致了子采样操作下的隐私放大。

引理 4：[通过子采样实现隐私放大] 如果机制在尺寸为大小的集合上关于替换关系满足DP，则满足DP。

缔约方（Parties）：我们将上图中的FLAME架构分为三个部分：1 ) 个用户，每个用户拥有一个维的本地更新向量，并运行一个输出为的本地随机数发生器。2 )混洗器——能够完美混洗接收消息并发送给分析器的服务器。3 )分析器，该服务器估计混洗消息到的均值并通过来更新第轮的全局模型。

信任边界（Trust Boundaries）：我们首先明确了FLAME中的信任边界。我们将观察者记为，它可以是任何能够观测到全局模型参数的一方。在curator model( DP-FL )中，信任边界位于和之间。在local model( LDP-FL )中，信任边界位于每个用户个体与其余用户之间。通过引入一个混洗器，FLAME避免了DP - FL对任何一方的完全信任，同时能够获得比LDP - FL更好的效用。

信任分离（Trust Separation）：进一步，在我们的框架FLAME中，我们明确了哪些是隐私信息，哪些人可以接触到这些信息。我们为FLAME设计了一个细粒度的信任分离方案，并在下表中与DP - FL和LDP - FL进行了比较。

具体来说，我们将每个本地更新的信息分离为：索引、相应索引的值和用户标识(即图2中的ID)。需要注意的是，当索引被选中并以值相关的的方式发送给混洗器时，索引可能是敏感的。因此，我们在FLAME中的隐私目标是使索引以数据不可见的方式被选择并且梯度的真实值对是不可见的。但是为了分发全局模型参数和接收本地消息，需要知道用户的隐式身份。来自的混洗消息不泄露用户身份且满足DP对抗。对于，DP具有后处理性质。在LDP - FL中，每个用户需要一个LDP的来实现这个目标。

FLAME框架（FLAME Framework）：我们在算法2中提出了我们的框架，包括三个构建过程：编码、混洗和分析。

在第8行，C是剪裁向量（clipping the vector）的阈值。我们用表示每个本地向量的本地隐私预算。我们用和分别表示分析器持有的公钥和私钥。下面通过第10行的和第15行的采用不同的策略的实现方式来设计不同的协议。需要说明的是，算法1中的可以作为基本的随机数发生器应用于，这与第( 18 )行的式( 1 )估计一致。一般的随机数发生器（e.g.拉普拉斯机制）也可以应用于这个函数，这并不影响我们后面的定理。

安全假设（Security Assumptions.）：我们假设混洗器和分析器是各自独立运行的（否则, FLAME退化为LDP - FL）。我们还假设密码原语是安全的，敌手从密文中学习任何信息都存在计算困难。

Simple Protocol (SS-Simple)： 我们首先在FLAME框架下提出维聚合的SS-Simple 。简言之，我们对一维协议进行了扩展，对每个维度进行随机化和聚合。由引理2的合成性质，R应该满足LDP，其中 。我们在SS-Simple的算法2中用和来实例化函数。函数简单地生成一个置换并输出 。

然后，我们对分析器持有的中心DP进行说明。根据引理1对或其他通用的的数值评估可以得到一个放大的中心隐私。由引理3，我们很容易得到定理1中的向量级组成。推论2提炼出了从到的放大。

定理 1： 对于任意相邻的数据集，它们在一个用户的维本地向量上存在差异，在SS - Simple协议中满足DP，其中

推论 2： 对于SS -Simple协议，当，放大的中心隐私为。

定理 2： 当且，满足DP，其中

然而，在多维情形下，我们无法得到与类似的定理。直观上，这是因为混洗隐私放大的证明依赖于有界大小的相邻数据集，而子采样可能导致两个大小不同的相邻数据集。

定理 3： 当且 时，满足DP，其中

命题 1： 各维度估计均值的标准差为.

由于所有维度级别的数据集都被填充到相同的大小，并且DP在定理3的放大中成立，因此我们在定理4中展示了向量级DP的组合。采样率记为。我们在推论3中提取了从到的放大效应。

定理 4： 对于任意一个本地用户向量不同的相邻数据集，SS-Double协议中的维向量聚合协议满足DP，其中

推论 3：对于SS - Double协议，当，放大的中心隐私为

隐私放大的仿真： 为了比较SS-Simple和SS-Double的隐私放大效果，我们对和相关放大后的隐私进行了可视化。如下图所示。

1）（SS - Simple）：引理1和定理1

2）（SS - Double）：定理3和4

为了与引理1中的有效条件保持一致，我们比较了每个扰动维度的本地隐私预算相同条件下的上述两种情况，记为SS-Simple和为SS-Double。在这种情况下，我们用放大比表示时的放大效应。可以观察到SS-Double boosts的双放大效应将比值从提高到，其具有更强的隐私放大效应。值得注意的是，对于除之外的其他随机化子对于定理4中的双放大仍然成立，只是在的取值上有所不同。我们在实验中展示了更多的数值评估。

因此，我们有动机在定义3中使用基于匿名的度量来限制和保护索引隐私。我们记维度的大小是否在下的Top-，以及指标是否由选取。第一个不等式将敌手的成功率与联系起来，而第二个不等式保证了概率不大于1。直观地说，当时，索引隐私性最强，因为观察不会增加对抗成功率。

定义 3： 机制提供维向量的索引隐私，当且仅当对任意我们有且。

为了实现索引隐私，需要控制的概率。给定先验知识，，如果每个用户向混洗器报告个维度，其中只有个索引为真实Top，则。将其代入定义中，有。因此，当设定时，满足top索引隐私。

在处理后的向量上施加，采样个Top指标作为集合，从其余的非Top维度中随机采样作为。当个真值被扰动时，每个维度的隐私预算分裂为。然后将每个真实Top 维的值扰动为。每个非顶层维度用填充。然后将维填充到和的列表中，并通过算法2中的第11行将其加密为个消息。

隐私分析： 首先，我们给出命题2和图4中和的关系。当时，实现了最强的索引隐私。对于SS-Double，在随机抽样机制下自然成立。对于无索引隐私的另一种极端情况，SS-Topk仍然提供了很强的隐私保证，因为混洗器除了知道Top个索引外什么都不知道。最新研究的工作表明，即使知道Top指标及其值，隐私攻击的可用性也会显著受损。

命题 2： top索引隐私的范围是，其中当时达到最强的索引隐私，当时没有实现索引隐私。

然后，我们阐明了索引隐私对混洗器和DP对分析器的兼容性。在算法3中使用，分析器只得到相同大小的每个维度的填充结果。因此，针对混洗器的index隐私不影响针对分析器的放大隐私DP。SS-Topk在相同的情况下共享SS - Double中的双重放大效应。

最后，我们讨论了索引隐私与通信成本以及效用之间的权衡。给定一个期望的top索引隐私，每个用户可以在图4中选择一个有效的来实现它。每个用户的带宽取决于。正如命题1所暗示的，估计效用依赖于虚拟填充大小。因此，给定，和，不影响均值估计的精度，因为虚拟值的个数是固定的。我们在定理5中证明了给定参数下的最强索引隐私性。

定理 5： 给定一个具有，的协议，它允许每个用户的最强索引隐私是，。

我们在MNIST数据集和，的逻辑回归模型上评估了学习性能。baseline包括非私有联邦平均( NP-FL ) [、带高斯机制的DP - FL (在有界DP定义下，我们将比较的灵敏度加倍)、带高斯机制的LDP - FL ( LDP )和拉普拉斯机制 ( LDP )以及我们提出的SS-Simple、SS-Double、SS-Topk三种协议。

三种协议之间的比较： 对于SS-Simple、SS-Double、SS-Topk，我们采用拉普拉斯机制作为每个维度的基本随机函数发生器。在SS-Simple中给定，各维度的隐私预算离散度；对于SS-Double和SS-Topk给定。双放大效应将对的隐私保护放大在一个epoch中从 DP (SS-Simple )提升到DP ( SS-Double / Topk )。与SS-Simple相比，SS-Double在更强的中心隐私性下，测试精度提高了。与SS-Double相比，在相同的中心隐私下，SS-Topk显著提高了的效用。根据定理5和图5中的，当时，协议允许每个用户的最大索引隐私度。

DP - FL / LDP比较：很明显，即使SS-Simple的baseline也比LDP - FL表现更好。我们观察到，在相同的中心隐私DP下，SS-Topk甚至取得了比DP - FL高的准确率。这是我们工作的一个key observation，因为针对一维任务的传统工作声称混洗模型只站在LDP和DP之间。

我们分析原因如下：1 ) Topk的作用：由于SS-Double不能超过DP - FL DP的性能，而SS-Topk可以，显然Top 提高了效用。2 )双放大效应：如果只统计SS-Topk的混洗放大，不统计SS-Topk的子采样放大，则。因此，我们引入DP - FLDP的另一个baseline。我们观察到这一行接近非私有版本，并且比SS-Topk具有更高的测试准确率。换句话说，如果只计算混洗的放大，SS-Topk不能比DP - FL表现更好。因此，我们验证了所提出的双重采样对于这种非平凡效用提升的效果。因此，我们得出结论，双重放大和Top提升都是比DP - FL更好的性能所必需的。

不同参数下的比较： 在忽略子采样放大效应的情况下，我们评估了其他超参数和隐私预算，结果见下图6，7和8。

1 )从图6中可以明显看出，每个维度更大的本地隐私预算导致更高的测试精度。

2 )在图7中，的比值越大，dummy padding注入的附加噪声越小。这验证了我们在命题1中的效用分析。因此，我们可以得出结论，是调节隐私和效用权衡的关键。

3 )在图8中，我们可以观察到越大，效用越好。当时，可以在2个epoch内提供 DP，与图5中NP - FL相比仅损失。

Privacy Amplification： 我们在图9和图10中用拉普拉斯机制的Bennett不等式来说明前面评估中的整体放大。

这验证了只要放大的界可以通过闭式解或数值计算得到，那么们的定理1，4和推论2，3对于任何本地随机数发生器就都是通用的。

综上所述，我们提出了第一个基于混洗模型的差分私有联邦学习框架FLAME，在不依赖任何可信服务器的情况下获得更好的效用。我们的隐私放大效应和私有Top 选择机制显著提高了高维环境下的测试准确率。